// 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
// 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
// left为加法的总和，right为减法的总和
// left + right = sum
// left - right = target
// left = (target + sum) / 2
function findTargetSumWays(nums, target) {
    // nums中都是非负整数
    let sum = nums.reduce((sum, cur) => sum + cur)
    if (Math.abs(target) > sum) {
        return 0
    }
    if ((target + sum) % 2) {
        return 0
    }
    let bagSize = (target + sum) / 2
    nums.sort((a, b) => a - b)
    let result = 0
    function backtracking(sum, startIndex) {
        for (let i = startIndex; i < nums.length; i++) {
            backtracking(sum + nums[i], i + 1)
        }
        if (sum > bagSize) {
            return
        }
        if (sum === bagSize) {
            result++
            return 
        }
    }
    backtracking(0, 0)
    return result
}

console.log(findTargetSumWays( [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 0))

// 思路2，动态规划
// 上面left，加法的总和即为背包的大小，问题转换为装满容量为left的背包，有几种方法
// 五部曲
// 1. `d[j]`,装满j有这么多的方法
// 2. 递推公式,`dp[j] += dp[j - nums[i]]`，组合类的问题都是这种公式
// 3. `dp[0] = 1`
// 4. 遍历顺序，外层是数组，内层是背包倒序
// 5. 举例
function findTargetSumWays2(nums, target) {
    let sum = nums.reduce((sum, cur) => sum + cur)
    if (Math.abs(target) > sum) {
        return 0
    }
    if ((target + sum) % 2) {
        return 0
    } 
    let bagSize = (target + sum) / 2
    let dp = new Array(bagSize + 1).fill(0)
    dp[0] = 1
    for (let i = 0; i < nums.length; i++) {
        for (let j = bagSize; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]]           
        }        
    }
    return dp[bagSize]
}

console.log(findTargetSumWays2([1, 1, 1, 1, 1], 3))

function findTargetSumWays3(nums, target) {
    let sum = nums.reduce((sum, cur) => sum + cur)
    if (Math.abs(target) > sum) {
        return 0
    }
    if ((target + sum) % 2) {
        return 0
    } 
    let bagSize = (target + sum) / 2
    let dp = new Array(nums.length).fill(0).map(item => new Array(bagSize + 1).fill(0))
    

    // 初始化最上行
    if (nums[0] <= bagSize) {
        dp[0][nums[0]] = 1
    }

    // 初始化最左列，最左列其他数值在递推公式中就完成了赋值
    /**
     * 如果有两个物品，物品0为0， 物品1为0，装满背包容量为0的方法有几种。
放0件物品
放物品0
放物品1
放物品0 和 物品1
     */
    dp[0][0] = 1
    let numZero = 0
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            numZero++
        }
        dp[i][0] = Math.pow(2, numZero)      
    }

    for (let i = 1; i < nums.length; i++) {
        for (let j = 1; j <= bagSize; j++) {
            if (j < nums[i]) {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
            }
        }   
    }
    return dp[nums.length - 1][bagSize]
}

console.log(findTargetSumWays3([1, 1, 1, 1, 1], 3))